Secret Handshakes permit trust to be established between two parties in non-trustworthy environments. For example, two field agents of the Central Intelligence Agency (“CIA”) may need to contact each other in the field, while retaining their anonymity, so that they are not discovered by a counter-intelligence agent. A secret handshake allows the CIA agents to mutually authenticate themselves to each other through the exchange of certain credential information according to a special protocol, where the exchange of the credential information through the protocol would not compromise their anonymity if it were exchanged with a non-agent that is unable to participate properly in the secret handshake.
Thus, secret handshakes involve the mutual verification of matching credential information possessed by two users. Generally, it is possible that separate entities or users own credentials that are derived from group membership (e.g., membership in the CIA), from the possession of some property, or from the possibility to generate or detect particular events. All of these characteristics (i.e., group membership, possession of a particular property, and the possibility to generate or detect a particular event) are referred to herein with the term “property.” When two entities interact, for example, by moving within the proximity of each other, by using a common resource, and so forth, they can perform a secret handshake to mutually verify credentials owned by the two users match, i.e., whether the two credentials are complementary according to some pre-defined definition of complementariness.
To assure the confidentiality, untraceability and anonymity of the credential information exchanged during a secret handshake the credentials to be matched can be exchanged in an encrypted and randomized form.
In addition, the current theoretical framework of secret handshakes does not provide a satisfactory model for credential revocation from a user. Thus, if credentials fall into the hands of an unauthorized user, the unauthorized user could pass himself off as the legitimate user, at which point, the attacker could conduct business on the behalf of the legitimate user to achieve malicious goals of the unauthorized user.
Revocation of users' credentials requires a way of uniquely labeling each credential, so that legitimate users can reject any handshake attempt containing credentials labeled as revoked. However, tagging credentials to tell them apart implies that the anonymity of users whose credentials are not to be revoked is also compromised. Thus, the ability to reliably revoke credentials could result in a high breach in the anonymity of users, which limits the applicability of secret handshake protocols.
Thus, it is desirable to provide a credential revocation mechanism to revoke compromised credentials and issue fresh credentials to a legitimate user, with no nasty consequence whatsoever.